BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Hadwiger's conjecture says that every Kt-minor free graph is (t−1)-colorable. This problem has been proved for t≤6 but remains open for t≥7. K7-minor free graphs have been proved to be 8-colorable (Albar & Gonçalves, 2013). We prove here that K7−-minor free graphs are 7-colorable, where K7− is the graph obtained from K7 by removing one edge.
In this note we investigate some matroid minor structure results. In particular, we present sufficient conditions, in terms of {\em triangles}, for a matroid to have either U2,4 or F7 or M(K5) as a minor.
We prove that any triangulation of a surface different from the sphere and the projective plane admits an orientation without sinks such that every vertex has outdegree divisible by three. This confirms a conjecture of Barát and Thomassen and is a step towards a generalization of Schnyder woods to higher genus surfaces.
We study graphs where each edge adjacent to a vertex of small degree (7 and 9, respectively) belongs to many triangles (4 and 5, respectively) and show that these graphs contain a complete graph (K_6 and K_7, respectively) as a minor. The second case settles a problem of Nevo (Nevo, 2007). Morevover if each edge of a graph belongs to 6 triangles then the graph contains a K_8-minor or contains K_{2,2,2,2,2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloration of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K_7-minor free graph is 8-colorable and every K_8-minor free graph is 10-colorable.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.