Premium
On the critical graph conjecture
Author(s) -
Yap Hian Poh
Publication year - 1980
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190040309
Subject(s) - valency , mathematics , combinatorics , vertex (graph theory) , conjecture , discrete mathematics , graph , philosophy , linguistics
Gol'dberg has recently constructed an infinite family of 3‐critical graphs of even order. We now prove that if there exists a p (≥4)‐critical graph K of odd order such that K has a vertex u of valency 2 and another vertex v ≠ u of valency ≤( p + 2)/2, then there exists a p ‐critical graph of even order.