On the divisibility of graphs
For a simple graph \(G=(V,E)\) and a vertex \(x \in V\), let \(H_1,H_2,\ldots ,H_k\) be the \(k\) \((\geq 1)\) components of the neighborhood \(N(x)\) of \(x\) in \(G\). Then the graph \(G_x\) is obtained from \(G\) by the transformation of removing \(x\) and adding \(k\) new non-adjacent vertices \(x_1,x_2,\ldots ,x_k\) (called copies of \(x\)) and making each \(x_i\) adjacent to all vertices in \(H_i\) \((1\leq i \leq k)\). In the resulting graph \(G_x\), the neighborhood of each copy \(x_i\) of \(x\) is connected. Using this transformation repeatedly one gets a graph \(\widetilde{G}\) in which no vertex has a disconnected neighborhood. The construction of \(\widetilde{G}\) takes \(O(|V|^2+ |V||E|)\) time and \(\omega(G) = \omega (\widetilde{G})\), where \(\omega \) is the clique number. NEWLINENEWLINENEWLINEA cricket is the graph consisting of a triangle with two pendant edges at one vertex of the triangle. The authors prove that for a cricket-free graph \(G\) without odd holes, \(\chi (G) \chi (\widetilde{G})\), where \(\chi \) is the chromatic number. NEWLINENEWLINENEWLINEA gem is \(K_1 \vee P_4\) and let \(F_1\) be the graph obtained by identifying an edge of \(K_4\) with an edge of another \(K_4\). The authors prove that the clique number of \((\text{gem},F_1)\)-free graphs can be computed in \(O(|V|^2+|V||E|)\) time. This class strictly contains the diamond-free graphs. They further deduce the validity of the strong perfect graph conjecture (SPGC) for (cricket, gem, \(F_1\))-free graphs. NEWLINENEWLINENEWLINELet \( F_2 = K_2\vee \overline{K}_3,\;F_4 = K_1\vee P_5\) and \(F_3\) be obtained by identifying two adjacent edges of a \(K_4\) with an edge each of two different triangles. All these graphs and the cricket contain a claw. The authors prove that the SPGC is true for \((\text{cricket},F_2,F_3,F_4)\)-free graphs, thus extending the result for claw-free graphs.
- Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Coloring the hypergraph of maximal cliques of a graph with no long path
- Some problems on induced subgraphs
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Chromatic bounds for some classes of 2 K₂-free graphs
- A transformation which preserves the clique number
- Study of the divisor graph. II
- Structure and colour in triangle-free graphs
- 2-divisibility of some odd hole free graphs
- Coloring graph classes with no induced fork via perfect divisibility
- A linear-time algorithm for clique-coloring planar graphs
- List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly
- The clique-perfectness and clique-coloring of outer-planar graphs
- Clique-transversal sets and clique-coloring in planar graphs
- Study of the divisor graph. III
- Clique-coloring claw-free graphs
- Subgraph-avoiding coloring of graphs
- scientific article; zbMATH DE number 1735669 (Why is no real title available?)
- scientific article; zbMATH DE number 5812 (Why is no real title available?)
- Coloring clique-hypergraphs of graphs with no subdivision of \(K_5\)
- On the divisibility graph for finite sets of positive integers
- scientific article; zbMATH DE number 7478551 (Why is no real title available?)
- A linear-time algorithm for clique-coloring problem in circular-arc graphs
- Complexity of clique coloring and related problems
- Brief survey on divisor graphs and divisor function graphs
- Divisibility and coloring of some \(P_5\)-free graphs
- Graphs of large chromatic number
- Graphs with girth 9 and without longer odd holes are 3-colourable
- On the chromatic number of a family of odd hole free graphs
- On the structure of perfectly divisible graphs
- On the structure of some classes of (P₂ P₃)-free graphs
- -boundedness and related problems on graphs without long induced paths: a survey
- The perfect divisibility and chromatic number of some odd hole-free graphs
- Odd clique minors and chromatic bounds of {\(3K_1\), paraglider}-free graphs
- On the structure of (dart, odd hole)-free graphs
- Tight bounds on the clique chromatic number
- On the structure of certain intersection graphs
- On the stability properties of linear dynamic time-varying unforced systems involving switches between parameterizations from topologic considerations via graph theory
- \(K_{4}\)-free graphs with no odd holes
This page was built for publication: On the divisibility of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957752)
