On the chromatic number of \(2 K_2\)-free graphs

DOI10.1016/j.dam.2018.09.030zbMath1401.05105OpenAlexW2900184847MaRDI QIDQ1634757

Christoph Brause, Ingo Schiermeyer, Bert Randerath, Elkin Vumar

Publication date: 18 December 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.09.030

zbMATH Keywords

chromatic number\(\chi\)-binding function\(2 K_2\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (17)

Square-free graphs with no induced fork ⋮ Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ On graphs with no induced five‐vertex path or paraglider ⋮ Coloring of some crown-free graphs ⋮ On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques ⋮ Chromatic bounds for some subclasses of \((P_3\cup P_2)\)-free graphs ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ Near optimal colourability on hereditary graph families ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Claw-free graphs. VI: Colouring
• The strong perfect graph theorem
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Recognizing claw-free perfect graphs
• On the coverings of graphs
• A bound on the chromatic number of graphs without certain induced subgraphs
• Colouring of \((P_3 \cup P_2)\)-free graphs
• Chromatic bounds for some classes of \(2 K_2\)-free graphs
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• Graph Theory and Probability
• The Independence Ratio of Regular Graphs
• On the chromatic number of (P_{5},windmill)-free graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t

This page was built for publication: On the chromatic number of \(2 K_2\)-free graphs