Relevant bibliographies by topics / K-chordal Graphs

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'K-chordal Graphs'

Author: Grafiati
Published: 4 June 2021
Last updated: 6 September 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'K-chordal Graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "K-chordal Graphs"

1

Fomin, Fedor V., and Petr A. Golovach. "Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs." Algorithmica 83, no. 7 (2021): 2170–214. http://dx.doi.org/10.1007/s00453-021-00822-x.

Full text
Abstract:
AbstractWe study algorithmic properties of the graph class $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e . More precisely, we identify a large class of optimization problems on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e solvable in time $$2^{{\mathcal{O}}(\sqrt{k}\log k)}\cdot n^{{\mathcal{O}}(1)}$$ 2 O ( k log k ) · n O ( 1 ) . Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , namely, $${\textsc {Interval}}{-ke}$$ I N T E R V A L - k e and $${\textsc {Split}}{-ke}$$ S P L I T - k e graphs.
APA, Harvard, Vancouver, ISO, and other styles
2

Lee, Chuan-Min. "Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs." Algorithms 14, no. 1 (2021): 22. http://dx.doi.org/10.3390/a14010022.

Full text
Abstract:
This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.
APA, Harvard, Vancouver, ISO, and other styles
3

PRADHAN, D. "COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS." Discrete Mathematics, Algorithms and Applications 04, no. 03 (2012): 1250045. http://dx.doi.org/10.1142/s1793830912500450.

Full text
Abstract:
In this paper, we consider minimum total domination problem along with two of its variations namely, minimum signed total domination problem and minimum minus total domination problem for chordal bipartite graphs. In the minimum total domination problem, the objective is to find a smallest size subset TD ⊆ V of a given graph G = (V, E) such that |TD∩NG(v)| ≥ 1 for every v ∈ V. In the minimum signed (minus) total domination problem for a graph G = (V, E), it is required to find a function f : V → {-1, 1} ({-1, 0, 1}) such that f(NG(v)) = ∑u∈NG(v)f(u) ≥ 1 for each v ∈ V, and the cost f(V) = ∑v∈V f(v) is minimized. We first show that for a given chordal bipartite graph G = (V, E) with a weak elimination ordering, a minimum total dominating set can be computed in O(n + m) time, where n = |V| and m = |E|. This improves the complexity of the minimum total domination problem for chordal bipartite graphs from O(n2) time to O(n + m) time. We then adopt a unified approach to solve the minimum signed (minus) total domination problem for chordal bipartite graphs in O(n + m) time. The method is also able to solve the minimum k-tuple total domination problem for chordal bipartite graphs in O(n + m) time. For a fixed integer k ≥ 1 and a graph G = (V, E), the minimum k-tuple total domination problem is to find a smallest subset TDk ⊆ V such that |TDk ∩ NG(v)| ≥ k for every v ∈ V.
APA, Harvard, Vancouver, ISO, and other styles
4

Panda, B. S., and D. Pradhan. "A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs." Discrete Mathematics, Algorithms and Applications 07, no. 02 (2015): 1550020. http://dx.doi.org/10.1142/s1793830915500202.

Full text
Abstract:
A set D ⊆ V is a restrained dominating set of a graph G = (V, E) if every vertex in V\D is adjacent to a vertex in D and a vertex in V\D. Given a graph G and a positive integer k, the restrained domination problem is to check whether G has a restrained dominating set of size at most k. The restrained domination problem is known to be NP-complete even for chordal graphs. In this paper, we propose a linear time algorithm to compute a minimum restrained dominating set of a proper interval graph. We present a polynomial time reduction that proves the NP-completeness of the restrained domination problem for undirected path graphs, chordal bipartite graphs, circle graphs, and planar graphs.
APA, Harvard, Vancouver, ISO, and other styles
5

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (2018): 64. http://dx.doi.org/10.14419/ijet.v7i4.10.20708.

Full text
Abstract:
For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c : V → {1, 2, . . .} such that c(u) 12≠"> c(v) for every edge uv ∈ E. For proper coloring, colors assigned must be minimum, but for Grundy coloring which should be maximum. In this instance, Grundy numbers of chordal graphs like Cartesian product of two path graphs, join of the path and complete graphs and the line graph of tadpole have been executed
APA, Harvard, Vancouver, ISO, and other styles
6

McKee, Terry A. "Characterizing k-chordal unichord-free graphs." Discrete Mathematics, Algorithms and Applications 10, no. 04 (2018): 1850043. http://dx.doi.org/10.1142/s179383091850043x.

Full text
Abstract:
The [Formula: see text]-chordal graphs, defined by no induced cycle having length greater than [Formula: see text], generalize the traditional chordal graphs (where [Formula: see text]), which Dirac characterized in 1961 by minimal separators always inducing complete subgraphs. The more recent unichord-free graphs, defined by no cycle having a unique chord, have been characterized by minimal separators always inducing edgeless subgraphs. This sharp contrast of minimal separators motivates a new concept of [Formula: see text]-unichord-free graphs, strengthening the unichord-free graphs (where [Formula: see text]). The class of all unichord-free graphs decomposes into subclasses that are simultaneously [Formula: see text]-chordal and [Formula: see text]-unichord-free, leading to characterizations of some of these subclasses and to open questions about their overall structure as [Formula: see text] and [Formula: see text] increase.
APA, Harvard, Vancouver, ISO, and other styles
7

Gunda, Spoorthy, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. "On the Parameterized Approximability of Contraction to Classes of Chordal Graphs." ACM Transactions on Computation Theory 13, no. 4 (2021): 1–40. http://dx.doi.org/10.1145/3470869.

Full text
Abstract:
A graph operation that contracts edges is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting k edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely, the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this article, we study the F -Contraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph G and an integer k , F -Contraction asks whether there exists X ⊆ E(G) such that G/X ∈ F and | X | ≤ k . Here, G/X is the graph obtained from G by contracting edges in X . We obtain the following results for the F - Contraction problem: • Clique Contraction is known to be FPT . However, unless NP⊆ coNP/ poly , it does not admit a polynomial kernel. We show that it admits a polynomial-size approximate kernelization scheme ( PSAKS ). That is, it admits a (1 + ε)-approximate kernel with O ( k f(ε)) vertices for every ε > 0. • Split Contraction is known to be W[1]-Hard . We deconstruct this intractability result in two ways. First, we give a (2+ε)-approximate polynomial kernel for Split Contraction (which also implies a factor (2+ε)- FPT -approximation algorithm for Split Contraction ). Furthermore, we show that, assuming Gap-ETH , there is no (5/4-δ)- FPT -approximation algorithm for Split Contraction . Here, ε, δ > 0 are fixed constants. • Chordal Contraction is known to be W[2]-Hard . We complement this result by observing that the existing W[2]-hardness reduction can be adapted to show that, assuming FPT ≠ W[1] , there is no F(k) - FPT -approximation algorithm for Chordal Contraction . Here, F(k) is an arbitrary function depending on k alone. We say that an algorithm is an h(k) - FPT -approximation algorithm for the F -Contraction problem, if it runs in FPT time, and on any input (G, k) such that there exists X ⊆ E(G) satisfying G/X ∈ F and | X | ≤ k , it outputs an edge set Y of size at most h(k) ċ k for which G/Y is in F .
APA, Harvard, Vancouver, ISO, and other styles
8

SHERMAN, DAVID, MING TSAI, CHENG-KUAN LIN, et al. "4-ORDERED HAMILTONICITY FOR SOME CHORDAL RING GRAPHS." Journal of Interconnection Networks 11, no. 03n04 (2010): 157–74. http://dx.doi.org/10.1142/s0219265910002787.

Full text
Abstract:
A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in 1997 by Ng and Schultz.13At the time, the only known examples were K4and K3,3. Some progress was made in 2008 by Mészáros,12when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010 a subclass of generalized Petersen graphs was shown to be 4-ordered by Hsu et al.,10with an infinite subset of this subclass being 4-ordered Hamiltonian, thus answering the open question. In this paper we find another infinite class of 3-regular 4-ordered Hamiltonian graphs, part of a subclass of the chordal ring graphs. In addition, we classify precisely which of these graphs are 4-ordered Hamiltonian.
APA, Harvard, Vancouver, ISO, and other styles
9

Markenzon, Lilian, Paulo Renato da Costa Pereira, and Christina F. E. M. Waga. "k-separator chordal graphs: leafage and subfamilies." International Transactions in Operational Research 20, no. 5 (2012): 681–88. http://dx.doi.org/10.1111/j.1475-3995.2012.00875.x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Goodarzi, Afshin. "Clique vectors of k-connected chordal graphs." Journal of Combinatorial Theory, Series A 132 (May 2015): 188–93. http://dx.doi.org/10.1016/j.jcta.2015.01.001.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "K-chordal Graphs"

1

Mathew, Rogers. "Boxicity And Cubicity : A Study On Special Classes Of Graphs." Thesis, 2012. https://etd.iisc.ac.in/handle/2005/2320.

Full text
Abstract:
Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1. The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable. Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work. 1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor. 2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation. 3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ). 4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average degree. 5. Boxicity of a k-leaf power is at most k -1. For every k, there exist k-leaf powers whose boxicity is exactly k - 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity 6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, k-chordal graph is bipartite and k-chordal thus implying that CBGs are closed under bipartite powering. 7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ log log Δ factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.
APA, Harvard, Vancouver, ISO, and other styles
2

Mathew, Rogers. "Boxicity And Cubicity : A Study On Special Classes Of Graphs." Thesis, 2012. http://etd.iisc.ernet.in/handle/2005/2320.

Full text
Abstract:
Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1. The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable. Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work. 1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor. 2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation. 3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ). 4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average degree. 5. Boxicity of a k-leaf power is at most k -1. For every k, there exist k-leaf powers whose boxicity is exactly k - 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity 6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, k-chordal graph is bipartite and k-chordal thus implying that CBGs are closed under bipartite powering. 7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ log log Δ factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "K-chordal Graphs"

1

Chepoi, Victor D., Feodor F. Dragan, and Chenyu Yan. "Additive Spanners for k-Chordal Graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-44849-7_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Watrigant, Rémi, Marin Bougeret, and Rodolphe Giroudeau. "Approximating the Sparsest k-Subgraph in Chordal Graphs." In Approximation and Online Algorithms. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-08001-7_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Kammer, Frank, and Torsten Tholey. "The k-Disjoint Paths Problem on Chordal Graphs." In Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-11409-0_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Dourisboure, Yon. "Compact Routing Schemes for Bounded Tree-Length Graphs and for k-Chordal Graphs." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-30186-8_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Bougeret, Marin, Nicolas Bousquet, Rodolphe Giroudeau, and Rémi Watrigant. "Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs." In SOFSEM 2014: Theory and Practice of Computer Science. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-04298-5_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Kosowski, Adrian, Bi Li, Nicolas Nisse, and Karol Suchan. "k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth." In Automata, Languages, and Programming. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31585-5_54.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

DeHaan, Ian, and Zachary Friggstad. "Approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs." In Lecture Notes in Computer Science. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-38906-1_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Conte, Alessio, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, and Kunihiro Wasa. "Efficient Enumeration of Maximal k-Degenerate Subgraphs in a Chordal Graph." In Lecture Notes in Computer Science. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-62389-4_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Amanathulla, Sk, and Madhumangal Pal. "L(h,k)-Labeling of Intersection Graphs." In Handbook of Research on Advanced Applications of Graph Theory in Modern Society. IGI Global, 2020. http://dx.doi.org/10.4018/978-1-5225-9380-5.ch007.

Full text
Abstract:
One important problem in graph theory is graph coloring or graph labeling. Labeling problem is a well-studied problem due to its wide applications, especially in frequency assignment in (mobile) communication system, coding theory, ray crystallography, radar, circuit design, etc. For two non-negative integers, labeling of a graph is a function from the node set to the set of non-negative integers such that if and if, where it represents the distance between the nodes. Intersection graph is a very important subclass of graph. Unit disc graph, chordal graph, interval graph, circular-arc graph, permutation graph, trapezoid graph, etc. are the important subclasses of intersection graphs. In this chapter, the authors discuss labeling for intersection graphs, specially for interval graphs, circular-arc graphs, permutation graphs, trapezoid graphs, etc., and have presented a lot of results for this problem.
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "K-chordal Graphs"

1

Araujo, Julio, Alexandre Cezar, Carlos Vinícius Gomes Costa Lima, Vinicius Fernandes Dos Santos, and Ana Shirley Ferreira Silva. "Proper Orientations of Chordal Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11080.

Full text
Abstract:
An orientation D of a graph G = (V, E) is a digraph obtained from G by replacing each edge by exactly one of the two possible arcs with the same end vertices. For each v ∈ V(G), the indegree of v in D, denoted by dD−(v), is the number of arcs with head v in D. An orientation D of G is proper if dD−(u) ≠ dD−(v), for all uv ∈ E(G). An orientation with maximum indegree at most k is called a k-orientation. The proper orientation number of G, denoted by χ→(G), is the minimum integer k such that G admits a proper k-orientation. We prove that determining whether χ→(G) ≤ k is NP-complete for chordal graphs of bounded diameter. We also present a tight upper bound for χ→(G) on split graphs and a linear-time algorithm for quasi-threshold graphs.
APA, Harvard, Vancouver, ISO, and other styles
2

Sobral, Gabriel A. G., Marina Groshaus, and André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.

Full text
Abstract:
In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K3free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K3-free and chordal bipartite graphs for any given 2-list assignment to edges.
APA, Harvard, Vancouver, ISO, and other styles
3

Santos, Tanilson D., Jayme Szwarcfiter, Uéverton S. Souza, and Claudson F. Bornstein. "On the Helly Property of Some Intersection Graphs." In Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação, 2021. http://dx.doi.org/10.5753/ctd.2021.15752.

Full text
Abstract:
An EPG graph G is an edge-intersection graph of paths on a grid. In this thesis, we analyze structural characterizations and complexity aspects regarding EPG graphs. Our main focus is on the class of B1-EPG graphs whose intersection model satisfies well-known the Helly property, called Helly-B1-EPG. We show that the problem of recognizing Helly-B1-EPG graphs is NP-complete. Besides, other intersection graph classes such as VPG, EPT, and VPT were also studied. We completely solve the problem of determining the Helly and strong Helly numbers of Bk-EPG graphs and Bk-VPG graphs for each non-negative integer k. Finally, we show that every Chordal B1-EPG graph is at the intersection of VPT and EPT.
APA, Harvard, Vancouver, ISO, and other styles
4

Andrade, Davi de, and Ana Silva. "On the Complexity of Subfall Coloring of Graphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16383.

Full text
Abstract:
Given a graph G and a proper k-coloring f of G, a b-vertex in f is a vertex that is adjacent to every color class but its own. If every vertex is a b-vertex, then f is a fall k-coloring; and G has a subfall k-coloring if there is an induced H $\subseteq$ G such that H has a fall k-coloring. The subfall chromatic number of G is the largest positive integer $\psi_{fs}(G)$ such that G has a subfall $\psi_{fs}(G)$-coloring. We prove that deciding if a graph G has a subfall k-coloring is NP-complete for k $\geq$ 4, and characterize graphs having a subfall 3-coloring. This answers a question posed by Dunbar et al. (2000) in their seminal paper. We also prove polinomiality for chordal graphs and cographs, and present a comparison with other known coloring metrics based on heuristics.
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography