Conditions for β-perfectness

Judith Keijsper; Meike Tewes

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 1, page 123-148
  • ISSN: 2083-5892

Abstract

top
A β-perfect graph is a simple graph G such that χ(G') = β(G') for every induced subgraph G' of G, where χ(G') is the chromatic number of G', and β(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., δ(H)+1). The vertices of a β-perfect graph G can be coloured with χ(G) colours in polynomial time (greedily). The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden induced subgraphs, for a graph to be β-perfect. We give new sufficient conditions and make improvements to sufficient conditions previously given by others. We also mention a necessary condition which generalizes the fact that no β-perfect graph contains an even hole.

How to cite

top

Judith Keijsper, and Meike Tewes. "Conditions for β-perfectness." Discussiones Mathematicae Graph Theory 22.1 (2002): 123-148. <http://eudml.org/doc/270446>.

@article{JudithKeijsper2002,
abstract = { A β-perfect graph is a simple graph G such that χ(G') = β(G') for every induced subgraph G' of G, where χ(G') is the chromatic number of G', and β(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., δ(H)+1). The vertices of a β-perfect graph G can be coloured with χ(G) colours in polynomial time (greedily). The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden induced subgraphs, for a graph to be β-perfect. We give new sufficient conditions and make improvements to sufficient conditions previously given by others. We also mention a necessary condition which generalizes the fact that no β-perfect graph contains an even hole. },
author = {Judith Keijsper, Meike Tewes},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chromatic number; colouring number; polynomial time; -perfect graph; coloring number; forbidden subgraph; even hole; claw-free graph},
language = {eng},
number = {1},
pages = {123-148},
title = {Conditions for β-perfectness},
url = {http://eudml.org/doc/270446},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Judith Keijsper
AU - Meike Tewes
TI - Conditions for β-perfectness
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 1
SP - 123
EP - 148
AB - A β-perfect graph is a simple graph G such that χ(G') = β(G') for every induced subgraph G' of G, where χ(G') is the chromatic number of G', and β(G') is defined as the maximum over all induced subgraphs H of G' of the minimum vertex degree in H plus 1 (i.e., δ(H)+1). The vertices of a β-perfect graph G can be coloured with χ(G) colours in polynomial time (greedily). The main purpose of this paper is to give necessary and sufficient conditions, in terms of forbidden induced subgraphs, for a graph to be β-perfect. We give new sufficient conditions and make improvements to sufficient conditions previously given by others. We also mention a necessary condition which generalizes the fact that no β-perfect graph contains an even hole.
LA - eng
KW - chromatic number; colouring number; polynomial time; -perfect graph; coloring number; forbidden subgraph; even hole; claw-free graph
UR - http://eudml.org/doc/270446
ER -

References

top
  1. [1] L.W. Beineke, Characterizations of derived graphs, J. Combin. Theory 9 (1970) 129-135, doi: 10.1016/S0021-9800(70)80019-9. Zbl0202.55702
  2. [2] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
  3. [3] M. Conforti, G. Cornuéjols, A. Kapoor and K. Vusković, Finding an even hole in a graph, in: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (1997) 480-485, doi: 10.1109/SFCS.1997.646136. 
  4. [4] G.A. Dirac, On rigid circuit graphs, Abh. Math. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776. Zbl0098.14703
  5. [5] P. Erdős and A. Hajnal, On the chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966) 61-99, doi: 10.1007/BF02020444. Zbl0151.33701
  6. [6] C. Figueiredo and K. Vusković, A class of β-perfect graphs, Discrete Math. 216 (2000) 169-193, doi: 10.1016/S0012-365X(99)00240-X. Zbl0952.05028
  7. [7] H.-J. Finck and H. Sachs, Über eine von H.S. Wilf angegebene Schranke für die chromatische Zahl endlicher Graphen, Math. Nachr. 39 (1969) 373-386, doi: 10.1002/mana.19690390415. Zbl0172.25704
  8. [8] T.R. Jensen and B. Toft, Graph colouring problems (Wiley, New York, 1995). Zbl0971.05046
  9. [9] S.E. Markossian, G.S. Gasparian and B.A. Reed, β-perfect graphs, J. Combin. Theory (B) 67 (1996) 1-11, doi: 10.1006/jctb.1996.0030. Zbl0857.05038

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.