The Experts below are selected from a list of 11199 Experts worldwide ranked by ideXlab platform

Maria Chudnovsky - One of the best experts on this subject based on the ideXlab platform.

  • induced Subgraphs of graphs with large chromatic number iii long holes
    arXiv: Combinatorics, 2015
    Co-Authors: Maria Chudnovsky, Alex Scott, Paul Seymour
    Abstract:

    We prove a 1985 conjecture of Gy\'arf\'as that for all $k,\ell$, every graph with sufficiently large chromatic number contains either a Complete Subgraph with $k$ vertices or an induced cycle of length at least $\ell$.

  • the strong perfect graph theorem
    Annals of Mathematics, 2006
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least five or the complement of one. The ?strong perfect graph conjecture? (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornu?ejols and Vuiskovi?c ? that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge?s conjecture cannot have either of these properties). In this paper we prove both of these conjectures.

  • the strong perfect graph theorem
    arXiv: Combinatorics, 2002
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures.

Robin Thomas - One of the best experts on this subject based on the ideXlab platform.

  • six critical graphs on the klein bottle
    Electronic Notes in Discrete Mathematics, 2008
    Co-Authors: Nathan Chenette, Luke Postle, Noah Streib, Carl Yerger, Robin Thomas, Daniel Kral, Jan Kyncl, Ken-ichi Kawarabayashi, Bernard Lidický
    Abstract:

    Abstract We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no Subgraph isomorphic to a member of the list. This answers a question of Thomassen [J. Comb. Theory Ser. B 70 (1997), 67–100] and implies an earlier result of Kral', Mohar, Nakamoto, Pangrac and Suzuki that an Eulerian triangulation of the Klein bottle is 5-colorable if and only if it has no Complete Subgraph on six vertices.

  • the strong perfect graph theorem
    Annals of Mathematics, 2006
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least five or the complement of one. The ?strong perfect graph conjecture? (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornu?ejols and Vuiskovi?c ? that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge?s conjecture cannot have either of these properties). In this paper we prove both of these conjectures.

  • the strong perfect graph theorem
    arXiv: Combinatorics, 2002
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures.

Paul Seymour - One of the best experts on this subject based on the ideXlab platform.

  • induced Subgraphs of graphs with large chromatic number iii long holes
    arXiv: Combinatorics, 2015
    Co-Authors: Maria Chudnovsky, Alex Scott, Paul Seymour
    Abstract:

    We prove a 1985 conjecture of Gy\'arf\'as that for all $k,\ell$, every graph with sufficiently large chromatic number contains either a Complete Subgraph with $k$ vertices or an induced cycle of length at least $\ell$.

  • the strong perfect graph theorem
    Annals of Mathematics, 2006
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least five or the complement of one. The ?strong perfect graph conjecture? (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornu?ejols and Vuiskovi?c ? that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge?s conjecture cannot have either of these properties). In this paper we prove both of these conjectures.

  • the strong perfect graph theorem
    arXiv: Combinatorics, 2002
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures.

Neil Robertson - One of the best experts on this subject based on the ideXlab platform.

  • the strong perfect graph theorem
    Annals of Mathematics, 2006
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least five or the complement of one. The ?strong perfect graph conjecture? (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornu?ejols and Vuiskovi?c ? that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge?s conjecture cannot have either of these properties). In this paper we prove both of these conjectures.

  • the strong perfect graph theorem
    arXiv: Combinatorics, 2002
    Co-Authors: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas
    Abstract:

    A graph G is perfect if for every induced Subgraph H, the chromatic number of H equals the size of the largest Complete Subgraph of H, and G is Berge if no induced Subgraph of G is an odd cycle of length at least 5 or the complement of one. The "strong perfect graph conjecture" (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures.

Hiroshi Mamitsuka - One of the best experts on this subject based on the ideXlab platform.

  • generalized sparse learning of linear models over the Complete Subgraph feature set
    IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017
    Co-Authors: Ichigaku Takigawa, Hiroshi Mamitsuka
    Abstract:

    Supervised learning over graphs is an intrinsically difficult problem: simultaneous learning of relevant features from the Complete Subgraph feature set, in which enumerating all Subgraph features occurring in given graphs is practically intractable due to combinatorial explosion. We show that 1) existing graph supervised learning studies, such as Adaboost, LPBoost, and LARS/LASSO, can be viewed as variations of a branch-and-bound algorithm with simple bounds, which we call Morishita-Kudo bounds; 2) We present a direct sparse optimization algorithm for generalized problems with arbitrary twice-differentiable loss functions, to which Morishita-Kudo bounds cannot be directly applied; 3) We experimentally showed that i) our direct optimization method improves the convergence rate and stability, and ii) L1-penalized logistic regression (L1-LogReg) by our method identifies a smaller Subgraph set, keeping the competitive performance, iii) the learned Subgraphs by L1-LogReg are more size-balanced than competing methods, which are biased to small-sized Subgraphs.