A contribution to queens graphs

Janos Barat

    Research output: Contribution to conferencePosterResearch

    Abstract

    A graph $G$ is a queens graph if the vertices of $G$ can be mapped to queens on the chessboard such that two vertices are adjacent if and only if the corresponding queens attack each other, i.e. they are in horizontal, vertical or diagonal position. We prove a conjecture of Beineke, Broere and Henning that the Cartesian product of an odd cycle and a path is a queens graph. We show that the same does not hold for two odd cycles. % is not representable in the same way. The representation of the Cartesian product of an odd cycle and an even cycle remains an open problem. We also prove constructively that any finite subgraph of the grid or the hexagonal grid is a queens graph.
    Original languageEnglish
    Publication date2004
    Publication statusPublished - 2004
    EventGraph Theory 2004: a conference in memory of Claude Berge - Paris
    Duration: 1 Jan 2004 → …

    Conference

    ConferenceGraph Theory 2004: a conference in memory of Claude Berge
    CityParis
    Period01/01/2004 → …

    Cite this

    Barat, J. (2004). A contribution to queens graphs. Poster session presented at Graph Theory 2004: a conference in memory of Claude Berge, Paris, .